The bibliographic references marked in the text by numbers within square brackets are listed at the end of the description.
1. Introduction
Over the last few years, the Extensible Markup Language [1] (XML) has become an increasingly popular format of describing hierarchical data. XML is a general-purpose markup language particularly suited for creating special-purpose markup languages that can describe the structure and hierarchy of many types of data files. XML is the lingua franca for information exchange over the Internet, and is also used to represent the internal data of many software systems. XML Schema [2] is a World Wide Web Consortium (W3C) recommendation that provides a mechanism for defining constraints on XML documents. An XML schema is in itself a valid XML document. It is a description of a type of XML documents, expressed in terms of constraints or rules on the structure and content of documents of that type, above and beyond the basic syntax constraints imposed by XML itself. An XML document is considered to be valid in relation to a specific schema if the XML document conforms to a set of constraints or rules defined by that XML schema.
One of the useful mechanisms provided by XML Schema is the ability to define identity constraints, including keys and foreign keys. These constraints, called ‘key’ and ‘keyref’, are similar to the ‘primary key’ and ‘foreign key’ constraints of databases, but their semantics is more complex due to the hierarchical nature of XML documents.
Key and keyref definitions use XML Path Language (XPath) 1.0 [3] expressions in order to specify paths to relevant nodes of the document. XPath is a concise (non-XML) syntax for addressing portions of an XML document. An XPath expression is a series of navigation steps and predicates. A navigation step leads from a node to its parent, children, descendants or siblings, and may also specify the tag of the desired target node. A predicate may be used to filter the set of nodes returned after the navigation step.
A key definition appears inside an element definition. This element is called the scope of the key. The key definition imposes constraints on the sub-tree of the scoping element. It looks as follows.
<xs:key name=“KeyName”><xs:selector xpath=XPATH_EXPRESSION/><xs:field xpath=XPATH_EXPRESSION/>... [possibly more fields]</xs:key>
The key definition includes a selector expression and one or more field expressions. These are expressions over a simple fragment of XPath [2], called “restricted XPath”. They do not contain predicates, and in each path the first location step may be “.//”, but the other steps may only be ‘self’ or ‘child’ steps. Also, for a field expression the path may end with an attribute. The selector expression is evaluated, with an instance s of the scoping element as a context node, to produce a set of nodes which we call the target node set of s (later we refer to these nodes as the selector-identified nodes of s). For each node in the target node set, every field expression must evaluate (relative to the node) to a node set containing exactly one node, of a simple type. Within an instance of the scoping element, there must not exist two distinct nodes of the target node set that have the same sequence of field values. Let K be a key, defined within the definition of an element e, with selector expression Sel and field expressions f1, . . . , fm. A document D is said to satisfy K if and only if for every instance n of e in D, the following hold. Let S be the set of nodes obtained from evaluating Sel in the context of n (S=Sel(n)). Then:                For each x ε S and for each fi, i=1 . . . m, fi evaluates to a single, simple-type node in the context of x.        For each x1, x2 ε S, if fi(x1)=fi(x2) for each i=1 . . . m then x1 and x2 are the same node.        
A keyref definition is very similar to a key definition. It appears within the definition of a scoping element and specifies selector and field expressions. It looks as follows:
<xs:keyref name=“KeyrefName” refer=“KeyName”><xs:selector xpath=“XPATH_EXPRESSION/><xs:field xpath=“XPATH_EXPRESSION”/>... [possibly more fields]</xs:keyref>
The “refer” attribute specifies the name of the key constraint that this keyref constraint refers to. Let n be an instance of the scoping element of a keyref. For each node u in the target node set of n, there must exist a node v, in some target node set of the referred key that has the same sequence of field values. The exact semantics is explained below.
For a simple example of the usefulness of key and keyref constraints, observe the schema depicted (informally) in FIG. 1. This schema defines a data store of libraries. Each library contains a list of books and a list of checkouts. A book is uniquely identified by the combination of its name and of the name of its author. Assuming in this example that the objective is to ensure the following two conditions:                1. A specific book appears only once within a library (and may have several copies, specified by its NumberOfCopies element).        2. A checkout must reference a book which is listed in the library.        
These objectives are achieved by defining, within the scope of the Library element, the following constraints:                1. A key, whose selector expression is .//Book and whose field expressions are ./Name and ./Author.        2. A keyref, whose selector expression is .//Checkout and whose field expressions are ./BookName and ./BookAuthor.        
1.1 Terminology
Let K be a key defined within the definition of an element e in a schema S.
Let KSel be the selector expression of K. Let KField1, . . . , KFieldk be the field expressions of K. Let D be a document.                The instances of e in D are called the scoping nodes of K.        Let n be a scoping node. Let Sn be the set of nodes which is the result of evaluating KSel in the context of n (Sn is sometimes called the “target node set”). Each x ε Sn is a selector-identified node (of n and K). Note that a selector-identified node of K may have several scoping nodes (if it is reachable from several different scoping nodes via the selector expression).        Let x be a selector-identified node of K. If a node f is returned when we evaluate a field expression in the context of x, then we call f a field of x. We call the sequence of values of the nodes returned when evaluating KField1, . . . , KFieldk in the context of x the key-sequence of x. Note that a node f may be a field of several different selector-identified nodes.        
These terms are also used for keyrefs.
1.2 Semantics of Key and Keyref Constraints
The semantics of keyref references, as described in [4], is quite complex:                These references are local to a scoping node of the keyref. Suppose n′ is a selector-identified node of a keyref scoping node n. Then a node n″ may be considered as being referenced by n′ only if n″ is a selector-identified node of the key, that has the same field values as n′, and at least one of the scoping nodes of n″ is either n or a descendant of n.        In a valid document, every selector-identified node of a keyref references (within a scoping node) exactly one selector-identified node of a key. To ensure this, there is a mechanism that resolves conflicts. Let n be a scoping node of a keyref KR that refers to a key K. There is a table, associated with n, which holds K's selector-identified nodes that may be referenced by KR's (or any other keyref that refers to K) selector-identified nodes whose scoping node is n. For each such node the table holds the node's key-sequence (i.e., the values of its fields). In order to construct the table for n, we compute the union of the tables of n's children. Also, if n is a scoping node of K, we add its selector-identified nodes, and key sequences, to the combined table. Then, if the combined table contains two or more rows with the same key-sequence ks (and different nodes), this is considered a conflict. The conflict is resolved as follows. All nodes with key-sequence ks that were added from the children's tables are removed. If there exists a selector-identified node of n with key-sequence ks then it stays in the table. Note that this conflict resolution may result in an empty table (since a key-sequence that appears only in child tables, and appears there more than once, will not appear in n's table).        
To illustrate these points, one can observe the document depicted in FIG. 2, where nodes of the document are marked by their tags. Suppose that this document conforms to a schema that defines a key, and a keyref that refers to it. Here, a (i.e., the node whose tag is ‘a’) is the scoping node of the keyref, and e is its selector-identified node. The c nodes are the scoping nodes of the key, and their c_ children are their selector-identified nodes (i.e., the selector expression is ./c_). The fields of a selector-identified node are its child nodes (whose values are shown in FIG. 2). Note that there are several c_ nodes with the same key-sequence. This does not violate the key constraint because these c_ nodes do not share a scoping node. There are three different c_ nodes in the document whose key-sequence is (3,4). e references the left-most of these c_ nodes. This is because the key-sequence (3,4) appears in the key tables of both children of d. Therefore, this key-sequence does not appear in the table of d. Thus, this key-sequence appears only in the table of the left child of b. The corresponding c node (marked with a circle in FIG. 2) percolates all the way up to the table of α, and therefore it is the node referenced by e. If one were to change the key-sequence of e to (1,2), the keyref constraint would be violated and the document would become invalid. This is because the key-sequence (1,2) does not appear in d's table (since it appears in the tables of both its children), and thus does not percolate up to α's table. This means that if we change e's key-sequence to (1,2), e will not reference any selector-identified node of the key.
As the popularity of XML increases, as an important tool for data exchange, it becomes more and more important to validate XML documents efficiently, with respect to XML Schema. In order for an XML document to be acceptable for a given application, the XML must be guaranteed to conform to a predefined structure, that is against an XML Schema. Current commercial XML validators enable validation of complete documents, but do not offer a mechanism for manipulating a document and incrementally validating the changes. Some work has been done regarding incremental validation of structural constraints, and also of non-XML Schema identity constraints.
It would be highly desirable to be able to validate only the changes that have been made to an XML document, and not start a validation procedure from scratch, as if the XML document has never been validated before.
It would also be desirable to offer a solution for verifying the validity of only XML Schema key keyref constraints, and in particular to incrementally validate key and keyref constraints only of an updated portion of a document.